package com.south.base.test.arithmetic.arrays;

import org.junit.Assert;
import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author Administrator
 * @date 2020/6/17 10:46
 */
public class Sum {
    /**
     * 组合总和
     * 给定一个无重复元素的数组 candidates 和一个目标数 target ，
     * 找出 candidates 中所有可以使数字和为 target 的组合。
     * candidates 中的数字可以无限制重复被选取。
     */
    @Test
    public void combinationSum() {
        Assert.assertEquals("[[2, 2, 3], [7]]", combinationSum(new int[]{2, 3, 6, 7}, 7).toString());
        Assert.assertEquals("[[2, 2, 2, 2], [2, 3, 3], [3, 5]]", combinationSum(new int[]{2, 3, 5}, 8).toString());
    }

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        if (candidates == null) {
            return res;
        }
        int len = candidates.length;
        if (len == 0) {
            return res;
        }
        Arrays.sort(candidates);
        int[] nums = new int[len];
        dfs(res, candidates, nums, 0, target, 0, len);
        return res;
    }

    public void dfs(List<List<Integer>> res, int[] candidates, int[] nums, int index, int target, int sum, int len) {
        if (sum == target) {
            List<Integer> content = new ArrayList<>();
            for (int i = 0; i < len; i++) {
                if (nums[i] == 0) {
                    continue;
                }
                int tmp = nums[i];
                while (tmp-- != 0) {
                    content.add(candidates[i]);
                }
            }
            res.add(content);
            return;
        }
        for (int i = index; i < len; i++) {
            if (sum + candidates[i] > target) {
                break;
            }
            nums[i]++;
            dfs(res, candidates, nums, i, target, sum + candidates[i], len);
            nums[i]--;
        }
    }

    /**
     * 组合总和 II
     * 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
     * candidates 中的每个数字在每个组合中只能使用一次。
     * 所有数字（包括目标数）都是正整数。
     * 解集不能包含重复的组合。
     */
    @Test
    public void combinationSum2() {
        Assert.assertEquals("[[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]", combinationSum2(new int[]{10, 1, 2, 7, 6, 1, 5}, 8).toString());
        Assert.assertEquals("[[1, 2, 2], [5]]", combinationSum2(new int[]{2, 5, 2, 1, 2}, 5).toString());
    }

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        if (candidates == null) {
            return res;
        }
        int len = candidates.length;
        if (len == 0) {
            return res;
        }
        Arrays.sort(candidates);
        int[] nums = new int[len];
        dfs2(res, candidates, nums, 0, target, 0, len);
        return res;
    }

    public void dfs2(List<List<Integer>> res, int[] candidates, int[] nums, int index, int target, int sum, int len) {
        if (sum == target) {
            List<Integer> content = new ArrayList<>();
            for (int i = 0; i < len; i++) {
                if (nums[i] == 0) {
                    continue;
                }
                int tmp = nums[i];
                while (tmp-- != 0) {
                    content.add(candidates[i]);
                }
            }
            if (!res.contains(content)) {
                res.add(content);
            }
            return;
        }
        for (int i = index; i < len; i++) {
            if (nums[i] > 0) {
                continue;
            }
            if (sum + candidates[i] > target) {
                break;
            }
            nums[i]++;
            dfs2(res, candidates, nums, i + 1, target, sum + candidates[i], len);
            nums[i]--;
        }
    }

    /**
     * 长度最小的子数组
     * 给定一个含有 n 个正整数的数组和一个正整数 s ，
     * 找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。
     * 如果不存在符合条件的连续子数组，返回 0。
     */
    @Test
    public void minSubArrayLen() {
        Assert.assertEquals(2, minSubArrayLen(7, new int[]{2, 3, 1, 2, 4, 3}));
        Assert.assertEquals(3, minSubArrayLen(11, new int[]{1, 2, 3, 4, 5}));
    }

    public int minSubArrayLen(int s, int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int res = Integer.MAX_VALUE, sum = 0, index = 0;
        for (int i = 0; i < nums.length; ++i) {
            sum += nums[i];
            while (sum >= s) {
                if (i + 1 - index < res) {
                    res = i + 1 - index;
                }
                sum -= nums[index];
                ++index;
            }
        }
        return res == Integer.MAX_VALUE ? 0 : res;
    }
}
